
/*
记忆化搜索
连接：https://leetcode.cn/problems/fibonacci-number/description/
题目：斐波那契数






  

   
    
*/
class Solution {
public:
    int memo[31];
    int fib(int n) {
        memset(memo,-1,sizeof memo);
        return dfs(n);
    }
    int dfs(int n)
    {
        if(memo[n]!=-1)
            return memo[n];
        if(n==0 || n==1)
        {
            memo[n] = n;
            return n;
        }
        memo[n] = dfs(n-1)+dfs(n-2);
        return memo[n];   
    }
};